package code.c02_list.clinkList;

/**
 * @author thinkpad - 83start
 * @version v1.0
 * @create 2022/9/25 23:08
 * @package code.c02_list.classwork.examples
 * @description 编写一个程序求解约瑟夫（Joseph）问题。有n个小孩围成一圈，给他们从1开始依次编号，
 * 从编号为1的小孩开始报数，数到第m个小孩出列，然后从出列的下一个小孩重新开始报数，数到第m个小孩又出列，
 * …，如此反复直到所有的小孩全部出列为止，求整个出列序列。
 * 如当n=6，m=5时的出列序列是5，4，6，2，3，1。
 */

public class Exam_2_22 {
    public static void main(String[] args) {
        int n, m;
        Joseph L;
        System.out.println("================== 测试1 ========================");
        n = 6;
        m = 3;
        L = new Joseph(n, m);
        System.out.println("n=" + n + ",m=" + m + "的约瑟夫序列：");
        System.out.println(L.Jsequence());

        System.out.println("================== 测试2 ========================");
        n = 8;
        m = 4;
        L = new Joseph(n, m);
        System.out.println("n=" + n + ",m=" + m + "的约瑟夫序列：");
        System.out.println(L.Jsequence());
    }

}

class Child {
    int no;
    Child next;

    public Child(int no) {
        this.no = no;
        this.next = null;
    }
}

class Joseph {
    int n, m;
    Child first;

    public Joseph(int n, int m) {
        this.n = n;
        this.m = m;
        first = new Child(1);

        Child p, t;

        t = first;
        for (int i = 2; i <= n; i++) {
            p = new Child(i);
            t.next = p;
            t = p;

        }
        t.next = first;
    }

    public String Jsequence() {
        String ans = "";
        int i, j;
        Child p, q;
        for (i = 1; i <= n; i++) {
            p = first;
            j = 1;
            while (j < m - 1) {
                j++;
                p = p.next;
            }
            q = p.next;
            ans += q.no + "\t";
            p.next = q.next;
            first = p.next;
        }

        return ans;
    }
}
